package baseclass.j_dp.dp.fullBag;

import java.util.Arrays;

/**
 * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额的所有组合数。
 * 如果没有任何一种硬币组合能组成总金额，返回 -1。
 * 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额:
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * <p>
 * 注意：1,2,2和2,2,1属于重复，不可以使用
 *
 * @date 2020/3/3 20:05
 */
public class Code02_ChangeMoneyCount {
    public static int process1(int[] coins, int index, int amount) {
        if (amount == 0) return 1;
        if (index >= coins.length) return 0;
        int res = 0;
        //对硬币，从第一个开始换，换1个coin0，2个coin0，.....,n个coin0 然后换coin1
        for (int count = 0; coins[index] * count <= amount; count++) {
            res += process1(coins, index + 1, amount - coins[index] * count);
        }
        return res;
    }

    /**
     * 暴力回溯的重复子问题：[1,2,3,....],
     * 换2个1和0个2   和  换0个1以及1个2  来到3时子问题重复
     * <p>
     * memo[i][j]表示前i种硬币能够凑成总金额 j 的组合数
     */
    public static int process2(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return 0;
        int[][] memo = new int[coins.length][amount + 1];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }
        return doProcess2(coins, 0, amount, memo);
    }

    public static int doProcess2(int[] coins, int index, int amount, int[][] memo) {
        if (amount == 0) return 1;
        if (index >= coins.length) return 0;
        if (memo[index][amount] != -1) return memo[index][amount];
        int res = 0;
        //对硬币，从第一个开始换，换1个coin0，2个coin0，.....,n个coin0 然后换coin1
        for (int count = 0; coins[index] * count <= amount; count++) {
            int temp = doProcess2(coins, index + 1, amount - coins[index] * count, memo);
            res += temp;
        }
        return memo[index][amount] = res;
    }


    /**
     * 完全背包问题转01背包：
     * 方程：dp[i][j] = dp[i-1][j]+dp[i][j-coins[i]]
     * <p>
     * 01背包方程：
     * dp[i][j] = dp[i-1][j]+dp[i-1][j-coins[i]]
     */
    private static int dp(int[] coins, int amount) {
        int[][] dp = new int[coins.length][amount + 1];
        //用coins[0]来说，是coins[0]的整数倍的都能组成是1
        for (int i = 0; i <= amount; i++) {
            int sum = coins[0] * i;
            if (sum > amount) break;
            dp[0][sum] = 1;
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                //对于当前使用的第i个硬币(对应coins[i]，
                // 账户余额为j的情况下，
                // 对于使用的硬币数还要再做一次循环
                for (int k = 0; k * coins[i] <= j; k++) {
                    dp[i][j] += dp[i - 1][j - k * coins[i]];
                    //完全背包如下
//                   dp[i][j] = Math.max(dp[i][j],price[i]+k*dp[i-1][j-k*weight[i]])
                }
            }
        }
        return dp[coins.length - 1][amount];
    }

    /**
     * 完全背包问题转01背包：
     * 方程：dp[i][j] = dp[i-1][j]+dp[i][j-coins[i]]
     * <p>
     * 01背包方程：
     * dp[i][j] = dp[i-1][j]+dp[i-1][j-coins[i]]
     */
    public static int dp1(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return amount == 0 ? 1 : 0;
        int[] dp = new int[amount + 1];
        //用coins[0]来说，是coins[0]的整数倍的都能组成是1
        for (int i = 0; i <= amount; i++) {
            int sum = coins[0] * i;
            if (sum > amount) break;
            dp[sum] = 1;
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2, 5};
        System.out.println(process1(coins, 0, amount));
        System.out.println(process2(coins, amount));
        System.out.println(dp(coins, amount));
        System.out.println(dp1(coins, amount));
        for (int i = 0; i < 10000; i++) {
            coins = generateRandomArray(3, 5);
            amount = (int) (Math.random() * 5);
            try {
                if (dp1(coins, amount) != dp(coins, amount)) {
                    System.out.println(Arrays.toString(coins));
                    System.out.println("amount = " + amount);
//                    break;
                }
            } catch (Exception e) {
                System.out.println(Arrays.toString(coins));
            }
        }
    }

    // for test
    private static int[] generateRandomArray(int maxSize, int maxValue) {
        //产生 [0-maxsize]随机长度的数组
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            //随机产生数据
            int value = (int) ((maxValue + 1) * Math.random());
            if (value == 0) value++;
            arr[i] = value;
        }
        return arr;
    }

}
